package base.datastructure.tree;


import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
 * 示例 1：
 * 输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
 * 输出：32
 * 示例 2：
 * 输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
 * 输出：23
 * 提示：
 * 树中节点数目在范围 [1, 2 * 104] 内
 * 1 <= Node.val <= 105
 * 1 <= low <= high <= 105
 * 所有 Node.val 互不相同
 */
public class PreOrderTraverse {

    /**
     * 前序遍历
     *
     * @param root
     * @param low
     * @param high
     * @return
     */
    public int preOrderTraverse(TreeNode root, int low, int high) {
        int sum = 0;
        if (root == null) {
            return sum;
        } else if (root.left == null && root.right == null) {
            System.out.println("val:" + root.val);
            if (root.val >= low && root.val <= high) {
                sum += root.val;
            }
            return sum;
        } else {
            System.out.println("val:" + root.val);
            if (root.val >= low && root.val <= high) {
                sum += root.val;
            }
            sum += preOrderTraverse(root.left, low, high);
            sum += preOrderTraverse(root.right, low, high);
        }
        return sum;
    }

    /**
     * 前序遍历递归版
     *
     * @param root
     * @param low
     * @param high
     * @return
     */
    public int preOrderTraverseMain(TreeNode root, int low, int high) {
        int sum = 0;
        if (root.val >= low && root.val <= high) {
            System.out.println("val:" + root.val);
            sum += root.val;
        }
        sum += preOrderTraverse(root.left, low, high);
        sum += preOrderTraverse(root.right, low, high);
        return sum;
    }

    /**
     * 前序遍历非递归版
     *
     * @param root
     * @param low
     * @param high
     * @return
     */
    public int preOrder(TreeNode root, int low, int high) {
        /**
         * 非前序遍历需要使用栈
         */
            Deque<TreeNode> deque = new LinkedList<>();
        int sum = 0;
        sum += root.val;
        deque.push(root);
        while (root != null || !deque.isEmpty()) {
            if (root != null) {
                if (root.val >= low && root.val <= high) {
                    System.out.println("val:" + root.val);
                    sum += root.val;
                }
                deque.push(root);
                root = root.left;
            } else {
                TreeNode node = deque.pop();
                root = node.right;
            }
        }
        return sum;
    }


}
